#include <iostream>
using namespace std;
 
struct Node {
	int nVal;
	struct Node* next;
};

struct Node *Head, *Tail;

// 尾部插入一个元素
void InsertTail(int val)
{
	struct Node* node = new struct Node();
	
	node->nVal = val;
	node->next = NULL;
	
	if (Head == NULL)
	{
		Head = node;
		Tail = node;
	}
	else
	{
		Tail->next = node;
		Tail = node;
	}
}

// 头部插入一个元素
void InsertHead(int val)
{
	struct Node* node = new struct Node();
	
	node->nVal = val;
	node->next = NULL;
	
	if (Head == NULL)
	{
		Head = node;
		Tail = node;
	}
	else
	{
		node->next = Head->next;
		Head->next = node;
	}
}

// 增序插入一个元素
void InsertAsc(int val)
{
	struct Node* node = new struct Node();
	
	node->nVal = val;
	node->next = NULL;
	
	if (Head == NULL)
	{
		cout << "Head" << " ";
		Head = node;
		Tail = node;
	}
	else
	{
		struct Node* temp = Head;
		if (temp->next == NULL)
		{
			temp->next = node;
			Tail = node;
			return;
		}
		while(temp->next != NULL)
		{
			if (temp->next->nVal > val)
			{
				node->next = temp->next;
				temp->next = node;
				break;
			}
			temp = temp->next;
			if (temp->next == NULL)
			{
				temp->next = node;
				Tail = node;
				return;
			}
		}
	}
}

// 倒序插入一个元素
void InsertDesc(int val)
{
	struct Node* node = new struct Node();
	
	node->nVal = val;
	node->next = NULL;
	
	if (Head == NULL)
	{
		cout << "Head" << " ";
		Head = node;
		Tail = node;
	}
	else
	{
		struct Node* temp = Head;
		if (temp->next == NULL)
		{
			temp->next = node;
			Tail = node;
			return;
		}
		while(temp->next != NULL)
		{
			if (temp->next->nVal < val)
			{
				node->next = temp->next;
				temp->next = node;
				break;
			}
			temp = temp->next;
			if (temp->next == NULL)
			{
				temp->next = node;
				Tail = node;
				return;
			}
		}
	}
}

// 指定位置插入一个元素
void InsertByPos(int val, int pos)
{
	struct Node* temp = Head;
	int n = 1;
	while (temp->next != NULL)
	{
		if (n < pos)
		{
			temp = temp->next;
			n ++;
		}
		else
		{
			break;
		}
	}
	
	if (n < pos)
	{
		return;
	}
	
	struct Node* node = new struct Node();
	
	node->nVal = val;
	node->next = NULL;
	
	node->next = temp->next;
	temp->next = node;
	
	if (node->next == NULL)
	{
		Tail = node;
	}
}

// 指定位置删除一个元素
void DelByPos(int pos)
{
	struct Node* temp = Head;
	int n = 1;
	while (temp->next != NULL)
	{
		if (n < pos)
		{
			temp = temp->next;
			n ++;
		}
		else
		{
			break;
		}
	}
	
	if (n < pos)
	{
		return;
	}
	
	if (temp->next == NULL)
	{
		return;
	}
	else
	{
		struct Node* t = temp->next;
		temp->next = temp->next->next;
		delete t;
		if (temp->next == NULL)
		{
			Tail = temp;
		}
	}
}

// 显示链表
void ShowList()
{
	struct Node* temp = Head;
	while(temp->next != NULL)
	{
		temp = temp->next;
		cout << temp->nVal << " ";
	}
	
	cout << endl;
}

// 清空链表
void DelList()
{
	struct Node* temp = Head;
	while(temp != NULL)
	{
		struct Node* now = temp;
		temp = temp->next;
		delete(now);
	}
	Head = NULL;
	Tail = NULL;
}

int main() {
	int a[7] = {4,5,3,8,9,2,6};

	Head = new struct Node();
	Tail = new struct Node();
	
	Head->next = NULL;
	Tail = Head;
	
	for (int i = 0; i < sizeof(a)/sizeof(int); i++)
	{
		InsertAsc(a[i]);
	}
	
	InsertByPos(11,1);

	ShowList();
	
	DelByPos(2);
	
	ShowList();
	
	return 0;
}
